Modelling, simulation and cryptography tools often require strings of random values or bits. For example, strings of random bits are often required for generating data encryption keys, simulating random processes, modelling complex natural phenomena. These strings of random bits may need to be unbiased, meaning every output value has the same chance of occurring (e.g. there is an equal chance of each output bit being a “1” or a “0”), or biased, meaning that the output values do not have the same chance of occurring (e.g. on average there will be twice as many “1”s as “0”s). As such, one specific example of an implementation of an embodiment may be the processing of random strings of values.
Computers, being deterministic systems, are not inherently suitable for producing strings of random values or bits. There are two main approaches to doing so: Pseudo-Random Number Generators (PRNGs) and True Random Number Generators (TRNGs).
TRNGs derive their ‘randomness’ from physical phenomena. Generally, TRNGs will do this by using measurements from a random natural occurrence to produce a string of random values or bits derived from the measured values. Typical examples of measured phenomena include atmospheric noise, radioactive decay and transmission of photons through a half-silvered mirror. As the outputs are determined by a natural process, which is inherently random, the output is truly random.
PRNGs are computer implemented algorithms, mathematical formulae or other methods which create a string of values or bits which may, to a certain extent, appear random. Examples of PRNG algorithms which output seemingly random strings of values include linear congruential generators, lagged Fibonacci generators, linear feedback shift registers and algorithms based on computational hardness assumptions.
PRNGs—frequently being computer implemented algorithms—are generally more efficient and can have a higher bitrate than TRNGs and so are often used in many applications where large strings of values or bits are required.
However, although such PRNGs may produce outputs which appear random, all PRNGs are, by their very definition, not truly random.
Biased strings of random bits are used in several cryptography techniques, for example in Quantum Key Distribution (QKD). QKD allows two parties to create and share a random secret key, or cipher, in a secure manner using quantum bits, or qubits. QKD theoretically allows the sender (often referred to as “Alice”) and receiver (often referred to as “Bob”) of the key to tell if an eavesdropper (often referred to as “Eve”) has intercepted the communication, compromising the key's security. This relies on the fact that a qubit cannot be measured without affecting the measured property. As such, any such alteration of the received qubits due to Eve's interference can be detected by Alice and Bob.
One method of implementing a QKD technique is the BB84 protocol. In order to effectively use some implementations of the BB84 protocol—in particular that using a decoy state protocol—a biased string of random bits or variables is required to select the frequency of pulses of certain intensities. Further possible applications for biased strings of random variables include modelling rare events, e.g. rain in the desert; simulating a card game on a computer; and modelling a random walk type problem, e.g. quantum scattering. These examples, along with other uses in the fields of cryptography, forecasting, gaming and research, require a string of values or bits with the following properties:                (a) the string of bits must meet a certain assessable quality of randomness;        (b) the string of bits must be statistically indistinguishable from a comparable (e.g. same value/bit rate and bias) string of values or bits generated by a TRNG; and        (c) the occurrence frequency (i.e. the bias) of the bits in the output must approximate that selected by a user.        
An additional efficiency optimisation requirement can also be taken into consideration, which is that:                (d) the generation of each bit in the output string must use on average a number of bits from the input string close to the entropy of the output string.        
Embodiments described herein can satisfy requirements (a) to (c), as well as the optimisation requirement (d).